package one;

/**
 * Given inorder and postorder traversal of a tree, construct the binary tree.
 * <p>
 * Note:
 * You may assume that duplicates do not exist in the tree.
 * <p>
 * ========================
 * Solution:
 * <p>
 * /**
 * Definition for binary tree
 * public class one.TreeNode {
 * int val;
 * one.TreeNode left;
 * one.TreeNode right;
 * one.TreeNode(int x) { val = x; }
 * }
 */

public class Day12_Construct_Binary_Tree_from_Inorder_and_Postorder_Traversal {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length != postorder.length) {
            return null;
        }

        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode build(int[] in, int sin, int ein, int[] post, int sp, int ep) {
        if (sin == ein) {
            return new TreeNode(in[sin]);
        }

        if (sin > ein) {
            return null;
        }

        int i = sin;
        for (i = sin; i <= ein; i++) {
            if (in[i] == post[ep]) {
                break;
            }
        }

        TreeNode node = new TreeNode(in[i]);
        //        node.left = build(in, sin, i - 1, post, sp, i - 1 - sin);
        node.left = build(in, sin, i - 1, post, sp, sp + i - 1 - sin);
        node.right = build(in, i + 1, ein, post, sp + i - sin, ep);
        return node;
    }
}
